package huawei.js2025;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * 流浪地球
 */
public class Question48 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int E = sc.nextInt();

        int[][] ints = new int[E][2];
        for (int i = 0; i < E; i++) {
            int T = sc.nextInt();
            int P = sc.nextInt();

            ints[i] = new int[]{T, P};
        }

        boolean[] fdj = new boolean[N];

        boolean allStart = false;

        int time = 0;
        Set<Integer> lastStart = new HashSet<>();
        while (!allStart) {

            Set<Integer> is = new HashSet<>();
            for (int i = 0; i < N; i++) {
                if (fdj[i]) {
                    // 左
                    if (i == 0) {
                        if (!fdj[N - 1]) {
                            is.add(N - 1);
                        }
                    } else {
                        if (!fdj[i - 1]) {
                            is.add(i - 1);
                        }
                    }

                    // 右边
                    if (i == N - 1) {
                        if (!fdj[0]) {
                            is.add(0);
                        }
                    } else {
                        if (!fdj[i + 1]) {
                            is.add(i + 1);
                        }
                    }
                }
            }

            for (int i = 0; i < E; i++) {
                if (time == ints[i][0] && !fdj[ints[i][1]]) {
                    is.add(ints[i][1]);
                }
            }

            for (int i : is) {
                fdj[i] = true;
            }

            boolean all = true;
            for (int i = 0; i < N; i++) {
                if (!fdj[i]) {
                    all = false;
                    break;
                }
            }

            if (all) {
                lastStart = is;
                allStart = true;
            } else {
                time += 1;
            }

        }

        System.out.println(time);
        System.out.println(lastStart);
    }
}
